package leetcode;

/**
 * 题目：最长回文子串
 * 链接：https://leetcode.cn/problems/longest-palindromic-substring/description/
 * ?envType=problem-list-v2&envId=dynamic-programming&
 * 示例 1：
 *
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 *
 * 输入：s = "cbbd"
 * 输出："bb"
 */
public class LongestPalindrome {

    public static void main(String[] args) {
        String s = "abb";
        String s1 = longestPalindrome(s);
        System.out.println(s1);
    }
    // 使用滑动窗口 or 双指针
    public static String longestPalindrome(String s) {
        String maxLongStr = "";
        if(s == null || s.length() == 0)
            return maxLongStr;
        if (s.length() == 1) {
            return s;
        }
        if (isPalindrome(s)) {
            return s;
        }else if(s.length() == 2){
            return s.substring(0, 1);
        }

        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                String subStr = s.substring(i, j);
                if (isPalindrome(subStr)) {
                    maxLongStr = maxLongStr.length() < subStr.length() ? subStr : maxLongStr;
                    System.out.println(maxLongStr);
                }
            }
        }
        return maxLongStr;
    }
    public static boolean isPalindrome(String s) {
        String news = s.toLowerCase().trim();
        if (news.isEmpty()) {
            return true;
        }
        if(news.length() == 1) {
            return true;
        }
        int start = 0, end = news.length() - 1;
        // 双指针
        while (start < end) {
            if (!Character.isLetterOrDigit(news.charAt(start)) || !Character.isLetterOrDigit(news.charAt(end))) {
                if (!Character.isLetterOrDigit(news.charAt(start))) {
                    start++;
                } else {
                    end--;
                }
            } else if (news.charAt(start) != news.charAt(end)) {
                return false;
            } else {
                start++;
                end--;
            }
        }
        return true;
    }
}
